#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: sort.py
@time: 2021/12/18 14:05
@desc:
'''


# 冒泡排序
def bubble_sort(nums: list):
    n = len(nums)
    for i in range(n):
        flag = True  # 是否有序
        for j in range(1, n - i):
            if nums[j - 1] > nums[j]:
                nums[j - 1], nums[j] = nums[j], nums[j - 1]
                flag = False

        if flag: return  # 可以剪枝


# 快速排序
"""
思路：通过Parition算法对数组进行操作，使得其返回一个枢轴，
枢轴左边的元素皆小于它，而右边皆大于他，递归的对枢轴左右部分进行同样的操作
自顶向下
"""
def quick_sort(nums: list, low, high):
    def pivot(nums, low, high):
        pivot = nums[low]
        while low < high:
            while low < high and nums[high] >= pivot: high -= 1
            nums[low] = nums[high]  # 若找到小于枢纽的则交换到low的位置
            while low < high and nums[low] <= pivot: low += 1
            nums[high] = nums[low]

        # 退出循环是low==high的时候，此时左边皆小于pivot，右边皆大于pivot，因此只要复原该元素即可
        nums[low] = pivot  # 还原枢纽元素
        return low
    if low < high:
        p = pivot(nums, low, high) # 整顿一次，整顿后p左边都小于p，右边则都大于p
        quick_sort(nums, low, p - 1)
        quick_sort(nums, p + 1, high)

# 选择排序
def select_sort(nums: list):
    min = 0
    n = len(nums)
    for i in range(n):
        min = i
        for j in range(i, n):
            if nums[j]<nums[min]:
                nums[min], nums[j] = nums[j], nums[min]
                min = j

# 归并排序
def merge_sort(nums: list, low, high):
    def merge(nums: list, low, mid, high):
        """
        将有序的两部分合并, [low,...mid], [mid+1, high]
        """
        # 拷贝数组
        t = [num for num in nums]
        # i, j 分别代表前半部分与后半部分. k代表重新插入时目前的位置
        i, j, k = low, mid+1, low
        while i<=mid and j<=high:
            if t[i]<t[j]:
                nums[k] = t[i]
                i += 1
                k += 1
            else:
                nums[k] = t[j]
                j += 1
                k += 1
        while i<=mid:
            nums[k] = t[i]
            i += 1; k+=1
        while j<=mid:
            nums[k] = t[j]
            j += 1; k+=1

    if low<high:
        mid = (low+high)//2
        merge_sort(nums, low, mid)
        merge_sort(nums, mid+1, high)
        merge(nums, low, mid, high)


if __name__ == '__main__':
    nums = [2, 3, 4, 1, 3, 4, 5, 6, 7, 8, 3, 2, 1]
    # bubble_sort(nums)
    # quick_sort(nums, 0, len(nums)-1)
    # select_sort(nums)
    merge_sort(nums, 0, len(nums)-1)
    print(nums)



